const args = [2, 3, 13, 17, 4, 19, 1]
console.log(arguments.callee.toString())
// ================================================快速排序（Quick Sort）================================================
const quick_sort = (arr) => {
  if (arr.length < 2) {
    return arr
  }
  const middle = Math.floor(arr.length / 2)
  const point = arr.splice(middle, 1)
  const left = [], right = []
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > point) {
      right.push(arr[i])
    } else {
      left.push(arr[i])
    }
  }
  return quick_sort(left).concat(point, quick_sort(right))
}
console.log('快速排序: ', JSON.stringify(quick_sort([...args])))

// ================================================冒泡排序（Bubble Sort）================================================
const bubble_sort = (arr) => {
  if (arr.length < 2) {
    return arr
  }
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return JSON.stringify(arr)
}
console.log('冒泡排序: ', bubble_sort([...args]))

// ================================================选择排序（Selection Sort）================================================
const selection_sort = (arr) => {
  if (arr.length < 2) {
    return arr
  }
  let minIndex, temp
  for (let i = 0; i < arr.length - 1; i++) {
    minIndex = i
    for (let j = i; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    if (i !== minIndex) {
      temp = arr[minIndex]
      arr[minIndex] = arr[i]
      arr[i] = temp
    }
  }
  return JSON.stringify(arr)
}
console.log('选择排序: ', selection_sort([...args]))

// ================================================插入排序（Insertion Sort）================================================
const insertion_sort = (arr) => {
  if (arr.length < 2) {
    return arr
  }
  let current, prevIndex
  for (let i = 1; i < arr.length; i++) {
    current = arr[i]
    prevIndex = i - 1
    while (prevIndex >= 0 && arr[prevIndex] > current) {
      arr[prevIndex + 1] = arr[prevIndex]
      prevIndex--
    }
    arr[prevIndex + 1] = current
  }
  return JSON.stringify(arr)
}
console.log('插入排序: ', insertion_sort([...args]))

// ================================================希尔排序（Shell Sort）================================================
const shell_sort = (arr) => {
  if (arr.length < 2) {
    return arr
  }
  let current, j
  for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < arr.length; i++) {
      j = i
      current = arr[i]
      while (j - gap >= 0 && arr[j - gap] > current) {
        arr[j] = arr[j - gap]
        j = j - gap
      }
      arr[j] = current
    }
  }

  return JSON.stringify(arr)
}
console.log('希尔排序: ', shell_sort([...args]))
